//
// Created by 123 on 2024/3/11.
//
#include <iostream>
#include <queue>

using namespace std;

typedef struct BiTNode {
    int data;
    BiTNode *lchild;
    BiTNode *rchild;
} BiTNode, *BiTree;

void show(BiTNode *node);

void level_show(BiTNode *node);

BiTNode *init_Node() {
    BiTNode *node = (BiTNode *) malloc(sizeof(BiTNode));
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

//先序遍历 preOrder
void preOrder(BiTNode *node);

//中序遍历 inOrder
void inOrder(BiTNode *node);

//后序遍历 postOrder
void postOrder(BiTNode *node);

//遍历到该节点的操作
void visit(BiTNode *node);





int main() {
    BiTree tree = init_Node();
    tree->data = 1;
    BiTNode *n2 = init_Node();
    n2->data = 2;
    BiTNode *n3 = init_Node();
    n3->data = 3;
    BiTNode *n4 = init_Node();
    n4->data = 4;
    BiTNode *n5 = init_Node();
    n5->data = 5;
    BiTNode *n6 = init_Node();
    n6->data = 6;
    BiTNode *n7 = init_Node();
    n7->data = 7;
    BiTNode *n8 = init_Node();
    n8->data = 8;
    BiTNode *n9 = init_Node();
    n9->data = 9;

    tree->lchild = n2;
    tree->rchild = n3;

    n2->lchild = n4;
    n2->rchild = n5;

    n3->lchild = n6;
    n3->rchild = n7;

    n4->lchild = n8;
    n4->rchild = n9;

    level_show(tree);
    show(tree);
    cout<<endl;
    cout<<"============================================="<<endl;
    cout<<"============================================="<<endl;
    cout<<"============================================="<<endl;
    cout<<"==================  先序  ======================"<<endl;
    preOrder(tree);
    cout<<"==================  中序  ======================"<<endl;
    inOrder(tree);
    cout<<"==================  后序  ======================"<<endl;
    postOrder(tree);



}

void visit(BiTNode *node) {
    cout << node->data << "   ";
}

void preOrder_ope(BiTNode *node) {
    if (node != NULL) {
        visit(node);
        preOrder_ope(node->lchild);
        preOrder_ope(node->rchild);
    }
}

//先序遍历 preorder
void preOrder(BiTNode *node) {
    preOrder_ope(node);
    cout << endl;
}


void inOrder_ope(BiTNode *node) {
    if (node != NULL) {
        inOrder_ope(node->lchild);
        visit(node);
        inOrder_ope(node->rchild);
    }
}

//中序遍历 inOrder
void inOrder(BiTNode *node) {
    inOrder_ope(node);
    cout << endl;
}

//后序遍历 postOrder
void postOrder_ope(BiTNode *node) {
    if (node != NULL) {
        postOrder_ope(node->lchild);
        postOrder_ope(node->rchild);
        visit(node);
    }
}
//后序遍历 postOrder
void postOrder(BiTNode *node) {
    postOrder_ope(node);
    cout<<endl;
}





void show(BiTNode *node) {
    if (node->lchild != NULL)
        show(node->lchild);
    cout << node->data << "  ";
    if (node->rchild != NULL)
        show(node->rchild);
}

void level_show(BiTNode *node) {
    queue<BiTNode *> que;
    que.push(node);
    while (!que.empty()) {
        int size=que.size();
        for (int i = 0; i < size; ++i) {
            BiTNode *n = que.front();
            que.pop();
            if (n->lchild != NULL) {
                que.push(n->lchild);
            }
            if (n->rchild != NULL) {
                que.push(n->rchild);
            }
            cout << n->data << "   ";
        }
        cout<<endl;
    }
    cout << endl;
}

